The random access technology is a technology for converting a given point on a time axis of a video stream into a recording position in the video stream, and enabling a playback of the video stream to be started from the recording position. The random access technology is a basic technology that is indispensably required for playing back a video stream recording on a recording medium such as BD-ROM or DVD-Video.
When the video stream is composed of picture data encoded by a variable-length encoding method, the amount of information per picture varies. As a result, “stream analysis” is required to achieve the random access to the video stream. Here, the “stream analysis” is a process in which a process of extracting a header of a picture from the stream body, reading the picture size from the header, and identifying the recording position of the next picture from the picture size is repeated a plurality of times until the recording position of a desired picture is identified. Such an analysis requires highly frequent accesses to the stream. As a result, it takes a considerable time before a random access is completed. For this reason, an entry map is required when above-mentioned conversion is executed for a random access. Here, the entry map is information that indicates a plurality of entry times on the time axis in correspondence with a plurality of entry positions in the video stream. With use of the entry map, for example, when the plurality of entry times in the entry map have a time accuracy of one second, it is possible to perform the random access with a high efficiency, namely, at the time accuracy of one second.
In a random access to a video stream, it is required to search for a picture that is present at the start of a GOP. A data structure for supporting the search of the starting picture of a GOP has been provided as prior art in the following document.    Document 1: Japanese Patent Application Publication No. 2000-228656